/* http://shootout.alioth.debian.org/u32q/benchmark.php?test=binarytrees&lang=all&box=1 */
/* adapted from C GNU gcc sample */

int32_t N = 10;

struct treeNode {
    treeNode	left;
    treeNode	right;
    int32_t	item;
};

treeNode
NewTreeNode(treeNode left, treeNode right, int32_t item)
{
    treeNode	tree = new(treeNode);
    tree.left = left;
    tree.right = right;
    tree.item = item;
    return tree;
}

int32_t
ItemCheck(treeNode tree)
{
    if (tree.left)
	return tree.item + ItemCheck(tree.left) - ItemCheck(tree.right);
    return tree.item;
}

treeNode
BottomUpTree(int32_t item, int32_t depth)
{
    if (depth > 0)
	return NewTreeNode(BottomUpTree(2 * item - 1, depth - 1),
			   BottomUpTree(2 * item, depth - 1),
			   item);
    return NewTreeNode(null, null, item);
}

int32_t		depth, minDepth, maxDepth, stretchDepth;
treeNode	stretchTree, longLivedTree, tempTree;

minDepth = 4;

if ((minDepth + 2) > N)
    maxDepth = minDepth + 2;
else
    maxDepth = N;

stretchDepth = maxDepth + 1;

stretchTree = BottomUpTree(0, stretchDepth);
print("stretch tree of depth %d\t check: %d\n",
      stretchDepth, ItemCheck(stretchTree));

longLivedTree = BottomUpTree(0, maxDepth);

for (depth = minDepth; depth <= maxDepth; depth += 2) {
    int32_t	i, iterations, check;

    iterations = 1 << (maxDepth - depth + minDepth);

    check = 0;

    for (i = 1; i <= iterations; i++) {
	tempTree = BottomUpTree(i, depth);
	check += ItemCheck(tempTree);

	tempTree = BottomUpTree(-i, depth);
	check += ItemCheck(tempTree);
    }

    print("%d\t trees of depth %d\t check: %d\n",
	  iterations * 2, depth, check);
}

print("long lived tree of depth %d\t check: %d\n",
      maxDepth, ItemCheck(longLivedTree));
